import java.awt.*;


 
public class Dijkstra 
	extends java.applet.Applet {
	private static final long serialVersionUID = 1L;
	GraphCanvas panel = new GraphCanvas(this);
	menu menu = new menu(this);   
	mensajes mensajes = new mensajes();	
	public void init() {
		setLayout(new BorderLayout(0, 0));
		add("Center",panel);add("South", mensajes);add("North", menu);
	}
	public void lock() {
		panel.lock();
		menu.lock();
	} 
	public void unlock() {
		panel.unlock();
		menu.unlock();
	} 
}


class menu extends Panel {

	private static final long serialVersionUID = 1L;
	Button b1 = new Button("borrar");   Button b2 = new Button("ejecutar");
    Button b3 = new Button("reset");
	Button b4 = new Button("grafo");
	Dijkstra parent;   
	boolean Locked=false;

	menu(Dijkstra myparent) {
		parent = myparent;
		setLayout(new GridLayout(1, 1, 2, 0));
		add(b4);add(b2);add(b3);add(b1); 
	}
	public boolean action(Event evt, Object arg) {
		if (evt.target instanceof Button) {
			if (((String)arg).equals("comenzar")) {
				if (!Locked) {
				
					parent.panel.stepalg();
				}
				else parent.mensajes.doctext.showline("cerrado");
			}
			if (((String)arg).equals("siguiente comenzar")) 
				parent.panel.nextstep();
			if (((String)arg).equals("reset")) { 
				parent.panel.reset();
				parent.mensajes.doctext.showline("referencia");
			}
			if (((String)arg).equals("borrar")) { 
				parent.panel.borrar();
				parent.mensajes.doctext.showline("referencia");
			}
			if (((String)arg).equals("ejecutar")) {
				if (!Locked)  
					parent.panel.runalg();
				else parent.mensajes.doctext.showline("cerrado");
			}
			if (((String)arg).equals("grafo")) {
				if (!Locked)   
					parent.panel.showgrafo();
				else parent.mensajes.doctext.showline("cerrado");
			} 
		}                   
		return true; 
	}

public void lock() {
		Locked=true;
	}
	public void unlock() {
		Locked=false;
	} 
}    

class mensajes extends Panel {
	private static final long serialVersionUID = 1L;
	DocText doctext = new DocText();
	mensajes() {
		setLayout(new BorderLayout(1, 1));
		add("Center", doctext);
	}
	public boolean action(Event evt, Object arg) {
		if (evt.target instanceof Choice) {
		}             
		return true;
	}
}

class DocText extends TextArea {
	private static final long serialVersionUID = 1L;
	
	
	final String comenzar = new String("INICIADO CON EXITO");
	final String grafo = new String("Puedes ejcutar el algoritmo para encontrar el camino mas optimo\n");
	final String hecho = new String("El algoritmo ha terminado, " +
			"las conexiones naranjas son el camino mas optimpo "+
			"para obtener\nel camino mas corto camino al " +
			"nodo de salida \n longitud del camino se escribe en el nodo.\n" +"Finalizado .");
	final String alguno = new String("El algoritmo ha terminado, " +
			"siga las aristas naranjas del node de entrada a cualquier nodo "+
			"para obtener\nel mas corto camino al " +
			"nodo. La longitud del camino se escribe en el nodo.\n" );
	final String ninguno = new String("El algoritmo ha terminado, " +
			"error en el procedimiento de resolucion.\n"); 
	final String maxnodos = new String("ERROR: "+ 
	"Maximo numero de nodos \n\n");
	final String cerrado = new String("ERROR: "+"Presiona Reset.\n"); 
	final String doc =  grafo;
	DocText() {
		super(4, 2);
		setText(doc);
	}

	public void showline(String str) {
           
		     if (str.equals("grafo"))            setText(grafo); 
		else if (str.equals("referencia"))          setText(doc);
		else if (str.equals("hecho"))               setText(hecho);   
		else if (str.equals("cerrado"))             setText(cerrado);
		else if (str.equals("maxnodos"))           setText(maxnodos);       
		else if (str.equals("ninguno"))               setText(ninguno);   
		else if (str.equals("alguno"))               setText(alguno);   
		else setText(str);
	}
}

class GraphCanvas extends Canvas 
  	implements Runnable {
	private static final long serialVersionUID = 1L;
	final int MAXNODOS = 25;
	final int MAX = MAXNODOS+1;
	final int NODOSIZE = 35;
	final int NODORADIX = 20;
	final int DIJKSTRA = 2;
	Point nodo[] = new Point[MAX];          
	int peso[][] = new int[MAX][MAX];     // peso 
	Point arista[][] = new Point[MAX][MAX];  // direccion
	Point startp[][] = new Point[MAX][MAX]; // inicio
	Point endp[][] = new Point[MAX][MAX];   //  final 
	float dir_x[][] = new float[MAX][MAX];  // direccion 
	float dir_y[][] = new float[MAX][MAX];  // direccion 

	boolean algedge[][] = new boolean[MAX][MAX];
	int dist[] = new int[MAX];
	int finaldist[] = new int[MAX];
	Color colornodo[] = new Color[MAX];
	boolean changed[] = new boolean[MAX];  
	int numchanged =0; 
	int neighbours=0;
    int comenzar=0;

	//Inicio Algoritmo
	int mindist, minnodo, minstart, minend;
	int numnodos=0;      
	int emptyspots=0;    
	int iniciografo=0;    
	int hitnodo;         
	int nodo1, nodo2;    
	Point thispoint=new Point(0,0); 
	Point oldpoint=new Point(0, 0); 
	
	boolean newarista = false;
	boolean movearista = false;
	boolean movestart = false;
	boolean borrarnodo = false;
	boolean movenodo = false;
	boolean performalg = false;
	boolean clicked = false;
	Font roman = new Font("roman", Font.BOLD, 13);
	Font helvetica= new Font("Helvetica", Font.BOLD, 13);
	FontMetrics fmetrics = getFontMetrics(roman);
	int h = (int)fmetrics.getHeight()/3;
	private Image offScreenImage;
	private Graphics offScreenGraphics;
	private Dimension offScreenSize;
	Thread algormo;
	int algoritmo;
	String showstring = new String("");
	boolean stepthrough=false;
	boolean Locked = false;
	Dijkstra parent;
	GraphCanvas(Dijkstra myparent) {
		parent = myparent;
		init();
		algoritmo=DIJKSTRA;
		setBackground(Color.black);
	}
	public void lock() {
		Locked=true;
	}
	public void unlock() {
		Locked=false;
	}
	public void start() {
		if (algormo != null) extracted();
	}
	@SuppressWarnings("deprecation")
	private void extracted() {
		algormo.resume();
	}
	public void init() {
		for (int i=0;i<MAXNODOS;i++) {
			colornodo[i]=Color.gray;
			for (int j=0; j<MAXNODOS;j++)
				algedge[i][j]=false;
		}
		colornodo[iniciografo]=Color.blue;
		performalg = false;
	}
	@SuppressWarnings("deprecation")
	public void borrar() {
		iniciografo=0;
		numnodos=0;
		emptyspots=0;
		init();
		for(int i=0; i<MAXNODOS; i++) {
			nodo[i]=new Point(0, 0);
			for (int j=0; j<MAXNODOS;j++)
				peso[i][j]=0;
		}
		if (algormo != null) algormo.stop();
		parent.unlock();
		repaint();
	}
	@SuppressWarnings("deprecation")
	public void reset() {
		init();
		if (algormo != null) algormo.stop();
		parent.unlock();
		repaint();
	}
	public void runalg() {
		parent.lock();
		initalg();
		performalg = true;
		algormo = new Thread(this);
		algormo.start();
	}
	public void stepalg() {
		parent.lock();
		initalg();
		performalg = true;
		nextstep();
	}
	public void initalg() {
		init();
		for(int i=0; i<MAXNODOS; i++) {
			dist[i]=-1;
			finaldist[i]=-1;
			for (int j=0; j<MAXNODOS;j++)
				algedge[i][j]=false;
		}
		dist[iniciografo]=0;
		finaldist[iniciografo]=0;
		comenzar=0;
	}
	public void nextstep() {
		finaldist[minend]=mindist;
		algedge[minstart][minend]=true;
		colornodo[minend]=Color.blue;
		comenzar++;
		repaint();
	}
	@SuppressWarnings("deprecation")
	public void stop() {
		if (algormo != null) algormo.suspend();
	}
	public void run() {
		for(int i=0; i<(numnodos-emptyspots); i++){
			nextstep();
			try { Thread.sleep(2000); }
			catch (InterruptedException e) {}
		}
		algormo = null;
	}
	@SuppressWarnings("deprecation")
	public void showgrafo() {
		int w, h;
		borrar();
		init();
		numnodos=21;
		emptyspots=0;
		for(int i=0; i<MAXNODOS; i++) {
			nodo[i]=new Point(0, 0);
			for (int j=0; j<MAXNODOS;j++)
				peso[i][j]=0;
		}
		w=this.size().width/8;
		h=this.size().height/8;
		nodo[0]=new Point(w, h);     nodo[1]=new Point(w, 3*h);
		nodo[2]=new Point(w, 7*h);   nodo[3]=new Point(2*w, h); 
		nodo[4]=new Point(2*w, 3*h); nodo[5]=new Point(3*w, 3*h);                             
		nodo[6]=new Point(2*w, 6*h); nodo[7]=new Point(5*w, h);	    
		nodo[8]=new Point(3*w, 5*h); nodo[9]=new Point(4*w, 4*h);
		nodo[10]=new Point(3*w, 7*h);nodo[11]=new Point(3*w, 7*h);
		nodo[12]=new Point(3*w, h);  nodo[13]=new Point(4*w, 6*h);
		nodo[14]=new Point(4*w, 2*h);nodo[15]=new Point(5*w, 3*h);
		nodo[16]=new Point(5*w, 5*h);nodo[17]=new Point(5*w, 7*h);
		nodo[18]=new Point(6*w, 4*h);nodo[19]=new Point(6*w, h);
		nodo[20]=new Point(6*w, 6*h); 
		
		peso[0][5]=23;  peso[5][12]=0; peso[15][16]=15;  peso[13][16]=24; 
		peso[0][4]=22;  peso[8][12]=3;   peso[14][7]=29; peso[4][8]=20; 
		peso[0][3]=17;  peso[10][9]=8;peso[17][20]=12;  peso[5][14]=20; 
		peso[1][10]=17; peso[9][14]=18; peso[13][17]=10; peso[16][17]=10; 
		peso[1][4]=4;   peso[9][13]=23;peso[12][15]=25;
		peso[2][6]=7;   peso[7][19]=34;
		peso[3][12]=23; peso[7][18]=40;peso[14][15]=9;
		peso[4][9]=6;   ;peso[10][8]=28;
		peso[6][10]=2;  peso[16][18]=23;peso[10][13]=19; 
		peso[6][8]=20;   peso[15][20]=52; peso[13][15]=19; 
		
		for (int i=0;i<numnodos;i++)
			for (int j=0;j<numnodos;j++)
				if (peso[i][j]>0)
					aristaupdate(i, j, peso[i][j]);
		repaint();
	}
	public boolean mouseDown(Event evt, int x, int y) {

		if (Locked)
			parent.mensajes.doctext.showline("cerrado");
		else {
			clicked = true;
			if (evt.shiftDown()) {
				if (nodohit(x, y, NODOSIZE)) {
					oldpoint = nodo[hitnodo];
					nodo1 = hitnodo;
					movenodo=true;
				}
			}
			else if (evt.controlDown()) {
				if (nodohit(x, y, NODOSIZE)) {
					nodo1 = hitnodo;
					if (iniciografo==nodo1) {
						movestart=true;
						thispoint = new Point(x,y);
						colornodo[iniciografo]=Color.gray;
					}
					else
						borrarnodo= true;
				}
			}
			else if (aristahit(x, y, 5)) {
				movearista = true;
				repaint();
			}
			else if (nodohit(x, y, NODOSIZE)) {
				if (!newarista) {
					newarista = true;
					thispoint = new Point(x, y);
					nodo1 = hitnodo;
				}
			}
			else if ( !nodohit(x, y, 50) && !aristahit(x, y, 50) )  {
				// dibuja nuevo nodo
				if (emptyspots==0) {
					if (numnodos < MAXNODOS)
						nodo[numnodos++]=new Point(x, y);
					else  parent.mensajes.doctext.showline("maxnodos");
				}
				else {
					// tomar un punto vacio en el array 
					int i;
					for (i=0;i<numnodos;i++)
						if (nodo[i].x==-100) break;
					nodo[i]=new Point(x, y);
					emptyspots--;
				}
			}
			else
				// mouseclick para cerrar 
				parent.mensajes.doctext.showline("close");
			repaint();
		}
		return true;
	}
	public boolean mouseDrag(Event evt, int x, int y) {
		if ( (!Locked) && clicked ) {
			if (movenodo) {
				nodo[nodo1]=new Point(x, y);
				for (int i=0;i<numnodos;i++) {
					if (peso[i][nodo1]>0) {
						aristaupdate(i, nodo1, peso[i][nodo1]);
					}
					if (peso[nodo1][i]>0) {
						aristaupdate(nodo1, i, peso[nodo1][i]);
					}
				}
				repaint();
			}
			else if (movestart || newarista) {
				thispoint = new Point(x, y);
				repaint();
			}
			else if (movearista) {
				changepeso(x, y);
				repaint();
			}
		}
		return true;
	}

	@SuppressWarnings("deprecation")
	public boolean mouseUp(Event evt, int x, int y) {
		if ( (!Locked) && clicked ) {
			if (movenodo) {
				nodo[nodo1]=new Point(0, 0);
				if ( nodohit(x, y, 50) || (x<0) || (x>this.size().width) || 
						(y<0) || (y>this.size().height) ) {
					nodo[nodo1]=oldpoint;
					parent.mensajes.doctext.showline("close");
				}
				else nodo[nodo1]=new Point(x, y);
				for (int i=0;i<numnodos;i++) {
					if (peso[i][nodo1]>0)
						aristaupdate(i, nodo1, peso[i][nodo1]);
					if (peso[nodo1][i]>0) 
						aristaupdate(nodo1, i, peso[nodo1][i]);
				}
				movenodo=false;
			}
			else if (borrarnodo) {
				nododelete();
				borrarnodo=false;
			}
			else if (newarista) {
				newarista = false;
				if (nodohit(x, y, NODOSIZE)) {
					nodo2=hitnodo;
					if (nodo1!=nodo2) {
						aristaupdate(nodo1, nodo2, 50);
						if (peso[nodo2][nodo1]>0) {
							aristaupdate(nodo2, nodo1, peso[nodo2][nodo1]);
						}
						parent.mensajes.doctext.showline("cambiar pesos");
					}
					else System.out.println(":)");
				}
			}
			else if (movearista) {
				movearista = false;
				if (peso[nodo1][nodo2]>0)
					changepeso(x, y);
			}
			else if (movestart) {
				if (nodohit(x, y, NODOSIZE))
					iniciografo=hitnodo;
				colornodo[iniciografo]=Color.red;
				movestart=false;
			}
			repaint();
		}
		return true;
	}
	public boolean nodohit(int x, int y, int dist) {
		for (int i=0; i<numnodos; i++)
			if ( (x-nodo[i].x)*(x-nodo[i].x) + 
					(y-nodo[i].y)*(y-nodo[i].y) < dist*dist ) {
				hitnodo = i;
				return true;
			}
		return false;
	}
	public boolean aristahit(int x, int y, int dist) {
		for (int i=0; i<numnodos; i++)
			for (int j=0; j<numnodos; j++) {
				if ( ( peso[i][j]>0 ) && 
						(Math.pow(x-arista[i][j].x, 2) + 
								Math.pow(y-arista[i][j].y, 2) < Math.pow(dist, 2) ) ) {
					nodo1 = i;
					nodo2 = j;
					return true;
				}
			}
		return false;
	}
	public void nododelete() {
		// borra un nodo y las aristas que entran/salen del nodo
		nodo[nodo1]=new Point(-100, -100);
		for (int j=0;j<numnodos;j++) {
			peso[nodo1][j]=0;
			peso[j][nodo1]=0;
		}
		emptyspots++;
	}
	public void changepeso(int x, int y) {

		int diff_x = (int)(20*dir_x[nodo1][nodo2]);
		int diff_y = (int)(20*dir_y[nodo1][nodo2]);
	
		boolean siga_x=false;
		if (Math.abs(endp[nodo1][nodo2].x-startp[nodo1][nodo2].x) >
		Math.abs(endp[nodo1][nodo2].y-startp[nodo1][nodo2].y) ) {
			siga_x = true;
		}
		
		if (siga_x) {
			int hbound = Math.max(startp[nodo1][nodo2].x, 
					endp[nodo1][nodo2].x)-Math.abs(diff_x);
			int lbound = Math.min(startp[nodo1][nodo2].x, 
					endp[nodo1][nodo2].x)+Math.abs(diff_x);
			
			if (x<lbound) { arista[nodo1][nodo2].x=lbound; }
			else if (x>hbound) { arista[nodo1][nodo2].x=hbound; }
			else arista[nodo1][nodo2].x=x;
			arista[nodo1][nodo2].y=
				(arista[nodo1][nodo2].x-startp[nodo1][nodo2].x) *
				(endp[nodo1][nodo2].y-startp[nodo1][nodo2].y)/
				(endp[nodo1][nodo2].x-startp[nodo1][nodo2].x) + 
				startp[nodo1][nodo2].y;
			peso[nodo1][nodo2]=
				Math.abs(arista[nodo1][nodo2].x-startp[nodo1][nodo2].x-diff_x)*
				100/(hbound-lbound);
		}
		else {
			int hbound = Math.max(startp[nodo1][nodo2].y, 
					endp[nodo1][nodo2].y)-Math.abs(diff_y);
			int lbound = Math.min(startp[nodo1][nodo2].y, 
					endp[nodo1][nodo2].y)+Math.abs(diff_y);
			if (y<lbound) { arista[nodo1][nodo2].y=lbound; }
			else if (y>hbound) { arista[nodo1][nodo2].y=hbound; }
			else arista[nodo1][nodo2].y=y;
			arista[nodo1][nodo2].x=
				(arista[nodo1][nodo2].y-startp[nodo1][nodo2].y) *
				(endp[nodo1][nodo2].x-startp[nodo1][nodo2].x)/
				(endp[nodo1][nodo2].y-startp[nodo1][nodo2].y) + 
				startp[nodo1][nodo2].x;
			peso[nodo1][nodo2]=
				Math.abs(arista[nodo1][nodo2].y-startp[nodo1][nodo2].y-diff_y)*
				100/(hbound-lbound);
		}
	}
	public void aristaupdate(int p1, int p2, int w) {
		int dx, dy;
		float l;
		peso[p1][p2]=w;
		dx = nodo[p2].x-nodo[p1].x;
		dy = nodo[p2].y-nodo[p1].y;
		// distancia entre pesos
		l = (float)( Math.sqrt((float)(dx*dx + dy*dy)));
		dir_x[p1][p2]=dx/l;
		dir_y[p1][p2]=dy/l;
		if (peso[p2][p1]>0) {
			startp[p1][p2] = new Point((int)(nodo[p1].x-5*dir_y[p1][p2]), 
					(int)(nodo[p1].y+5*dir_x[p1][p2]));
			endp[p1][p2] = new Point((int)(nodo[p2].x-5*dir_y[p1][p2]), 
					(int)(nodo[p2].y+5*dir_x[p1][p2]));
		}
		else {
			startp[p1][p2] = new Point(nodo[p1].x, nodo[p1].y);
			endp[p1][p2] = new Point(nodo[p2].x, nodo[p2].y);
		}
		int diff_x = (int)(Math.abs(20*dir_x[p1][p2]));
		int diff_y = (int)(Math.abs(20*dir_y[p1][p2]));
		if (startp[p1][p2].x>endp[p1][p2].x) {
			arista[p1][p2] = new Point(endp[p1][p2].x + diff_x +
					(Math.abs(endp[p1][p2].x-startp[p1][p2].x) - 2*diff_x )*
					(100-w)/100 , 0);
		}
		else {
			arista[p1][p2] = new Point(startp[p1][p2].x + diff_x +
					(Math.abs(endp[p1][p2].x-startp[p1][p2].x) - 2*diff_x )*
					w/100, 0);
		}
		if (startp[p1][p2].y>endp[p1][p2].y) {
			arista[p1][p2].y=endp[p1][p2].y + diff_y +
			(Math.abs(endp[p1][p2].y-startp[p1][p2].y) - 2*diff_y )*
			(100-w)/100;
		}
		else {
			arista[p1][p2].y=startp[p1][p2].y + diff_y +
			(Math.abs(endp[p1][p2].y-startp[p1][p2].y) - 2*diff_y )*
			w/100;
		}
	}

	public String intToString(int i) {
		char c=(char)((int)'a'+i);
		return ""+c;
	}
	public final synchronized void update(Graphics g) {
		@SuppressWarnings("deprecation")
		Dimension d=size();
		if ((offScreenImage == null) || (d.width != offScreenSize.width) ||
				(d.height != offScreenSize.height)) {
			offScreenImage = createImage(d.width, d.height);
			offScreenSize = d;
			offScreenGraphics = offScreenImage.getGraphics();
		}
		offScreenGraphics.setColor(Color.black);//color fondo
		offScreenGraphics.fillRect(0, 0, d.width, d.height);
		paint(offScreenGraphics);
		g.drawImage(offScreenImage, 0, 0, null);
	}
	public void drawarista(Graphics g, int i, int j) {
		int x1, x2, x3, y1, y2, y3;
		// calcular flecha
		x1= (int)(arista[i][j].x - 3*dir_x[i][j] + 6*dir_y[i][j]);
		x2= (int)(arista[i][j].x - 3*dir_x[i][j] - 6*dir_y[i][j]);
		x3= (int)(arista[i][j].x + 6*dir_x[i][j]);
		y1= (int)(arista[i][j].y - 3*dir_y[i][j] - 6*dir_x[i][j]);
		y2= (int)(arista[i][j].y - 3*dir_y[i][j] + 6*dir_x[i][j]);
		y3= (int)(arista[i][j].y + 6*dir_y[i][j]);
		int flecha_x[] = { x1, x2, x3, x1 };
		int flecha_y[] = { y1, y2, y3, y1 };
		// algoritmo cambiar color
		if (algedge[i][j]) g.setColor(Color.green);
		// dibuja arista
		g.drawLine(startp[i][j].x, startp[i][j].y, endp[i][j].x, endp[i][j].y);
		g.fillPolygon(flecha_x, flecha_y, 4);
		// escribe el peso de la arista en una posicion apropiada
		int dx = (int)(Math.abs(7*dir_y[i][j]));
		int dy = (int)(Math.abs(7*dir_x[i][j]));
		String str = new String("" + peso[i][j]);
		g.setColor(Color.white);//color aristas
		if ((startp[i][j].x>endp[i][j].x) && (startp[i][j].y>=endp[i][j].y))
			g.drawString( str, arista[i][j].x + dx, arista[i][j].y - dy);
		if ((startp[i][j].x>=endp[i][j].x) && (startp[i][j].y<endp[i][j].y))
			g.drawString( str, arista[i][j].x - fmetrics.stringWidth(str) - dx , 
					arista[i][j].y - dy);
		if ((startp[i][j].x<endp[i][j].x) && (startp[i][j].y<=endp[i][j].y))
			g.drawString( str, arista[i][j].x - fmetrics.stringWidth(str) , 
					arista[i][j].y + fmetrics.getHeight());
		if ((startp[i][j].x<=endp[i][j].x) && (startp[i][j].y>endp[i][j].y))
			g.drawString( str, arista[i][j].x + dx, 
					arista[i][j].y + fmetrics.getHeight() );
	}

	public void detailsDijkstra(Graphics g, int i, int j) {
		// checar si el nodo tiene la siguiente minima distancia al nodo_inicial
		if ( (finaldist[i]!=-1) && (finaldist[j]==-1) ) {
			g.setColor(Color.magenta);//color camino
			if ( (dist[j]==-1) || (dist[j]>=(dist[i]+peso[i][j])) ) {
				if ( (dist[i]+peso[i][j])<dist[j] ) {
					changed[j]=true;
					numchanged++;
				}
				dist[j] = dist[i]+peso[i][j];
				colornodo[j]=Color.red;//color nodo           
				if ( (mindist==0) || (dist[j]<mindist) ) {
					mindist=dist[j];
					minstart=i;
					minend=j;
				}
			}
		}
		else g.setColor(Color.orange);
	}
	public void endstepDijkstra(Graphics g) {
		// despliega distancias parcial y total de los nodos, ajusta la distancia final
		
		for (int i=0; i<numnodos; i++)
			if ( (nodo[i].x>0) && (dist[i]!=-1) ) {
				String str = new String(""+dist[i]);
				g.drawString(str, nodo[i].x - (int)fmetrics.stringWidth(str)/2 -1, 
						nodo[i].y + h);
				if (finaldist[i]==-1) {
					neighbours++;  
					if (neighbours!=1)
						showstring = showstring + ", ";
					showstring = showstring + intToString(i) +"=" + dist[i];
				} 
			}
		showstring = showstring + ". ";

		if ( (comenzar>1) && (numchanged>0) ) {
			if (numchanged>1)
				showstring = showstring + "Note que las distancias a ";
			else showstring = showstring + "Note que la distancia a ";
			for (int i=0; i<numnodos; i++)
				if ( changed[i] )
					showstring = showstring + intToString(i) +", ";
			if (numchanged>1)
				showstring = showstring + "han cambiado!\n";
			else showstring = showstring + "ha cambiado!\n";
		}
		else showstring = showstring + " "; 
		if (neighbours>1) { 
			showstring = showstring + "El nodo " + intToString(minend) + 
			" tiene un peso minimo.\n";
			int newcaminos=0;
			for (int i=0; i<numnodos; i++) 
				if ( (nodo[i].x>0) && (peso[i][minend]>0) && ( finaldist[i] == -1 ) )
					newcaminos++; 
			if (newcaminos>0) 
				showstring = showstring + "Cualquier otro camino a " + intToString(minend) + 
				" visita otro nodo de la red, y sera mas largo que " +  mindist + ".\n";
			else showstring = showstring + 
			"No hay  aristas entrando a "+
			intToString(minend) + ".\n";
		}
		else {
			boolean morenodos=false;
			for (int i=0; i<numnodos; i++) 
				if ( ( nodo[i].x>0 ) && ( finaldist[i] == -1 ) && ( peso[i][minend]>0 ) )
					morenodos=true; 
			boolean bridge=false;
			for (int i=0; i<numnodos; i++) 
				if ( ( nodo[i].x>0 ) && ( finaldist[i] == -1 ) && ( peso[minend][i]>0 ) )
					bridge=true; 
			if ( morenodos && bridge ) 
				showstring = showstring + "Dado que este nodo forma un 'puente' a "+
				"los nodos restantes,\ntienen un camino mas largo.\n";     
			else if ( morenodos && (!bridge) ) 
				showstring = showstring + "Los nodos grises restantes no tienen conexion.\n";
			else showstring = showstring + "No hay otras aristas entrando a "+
			intToString(minend) + ".\n"; 
		}
		showstring = showstring + "Node " + intToString(minend) + 
		" sera coloreado verde para indicar que " + mindist + 
		" es el camino mas optimo a " + intToString(minend) +"."; 
		parent.mensajes.doctext.showline(showstring);       
	}
	public void detailsalg(Graphics g, int i, int j) {
		if (algoritmo==DIJKSTRA)
			detailsDijkstra(g, i, j);
	}
	@SuppressWarnings("deprecation")
	public void endstepalg(Graphics g) {
		if (algoritmo==DIJKSTRA)
			endstepDijkstra(g);
		if ( ( performalg ) && (mindist==0) ) {
			if (algormo != null) algormo.stop();
			int nalcanzable = 0;
			for (int i=0; i<numnodos; i++)
				if (finaldist[i] > 0)
					nalcanzable++;
			if (nalcanzable == 0)
				parent.mensajes.doctext.showline("ninguno");
			else if (nalcanzable< (numnodos-emptyspots-1))
				parent.mensajes.doctext.showline("alguno");
			else
				parent.mensajes.doctext.showline("hecho");
		} 
	}
	public void paint(Graphics g) {
		mindist=0;
		minnodo=MAXNODOS;
		minstart=MAXNODOS;
		minend=MAXNODOS;
		for(int i=0; i<MAXNODOS; i++) 
			changed[i]=false;
		numchanged=0;
		neighbours=0;
		g.setFont(helvetica);
		g.setColor(Color.white);
		if (comenzar==1)
			showstring="analizando las aristas  " +
			" el nodo_inicial.\nLa distancia a: ";
		else 
			showstring="comenzar " + comenzar + ":  verificando los nodos cercanos " +
			"nodos que ya tienen una distancia final ." +
			"\nLa distancia : ";
		// dibuja una nueva arista en la posicion del mouse
		if (newarista)
			g.drawLine(nodo[nodo1].x, nodo[nodo1].y, thispoint.x, thispoint.y);
		// dibuja todas las aristas
		for (int i=0; i<numnodos; i++)
			for (int j=0; j<numnodos; j++)
				if (peso [i][j]>0) {
					if (performalg)
						detailsalg(g, i, j);
					drawarista(g, i, j);
				}
		if (movearista && peso[nodo1][nodo2]==0) {
			drawarista(g, nodo1, nodo2);
			g.drawLine(startp[nodo1][nodo2].x, startp[nodo1][nodo2].y, 
					endp[nodo1][nodo2].x, endp[nodo1][nodo2].y);
		}
		// dibuja los nodos
		for (int i=0; i<numnodos; i++)
			if (nodo[i].x>0) {
				g.setColor(colornodo[i]);
				g.fillOval(nodo[i].x-NODORADIX, nodo[i].y-NODORADIX, 
						NODOSIZE, NODOSIZE);
			}
		// refleja el nodo_inicial que se mueve
		g.setColor(Color.white);//color letra nodos
		if (movestart)
			g.fillOval(thispoint.x-NODORADIX, thispoint.y-NODORADIX, 
					NODOSIZE, NODOSIZE);
		if (performalg) endstepalg(g);
		g.setFont(helvetica);
		for (int i=0; i<numnodos; i++)
			if (nodo[i].x>0) {
				g.setColor(Color.black);
				g.drawOval(nodo[i].x-NODORADIX, nodo[i].y-NODORADIX, 
						NODOSIZE, NODOSIZE);
				g.setColor(Color.white);
				g.drawString(intToString(i), nodo[i].x-20, nodo[i].y-20);
			}
	}
}

















